1. Field of the Invention
The invention relates to a circuit and a method for forwarding data packets in a network.
2. Description of the Related Art
When forwarding data packets in a network, particularly in an IP network, an important and also most critical functionality of the router or IP network router used is to find which output port is to be used to forward a received data packet, so that it finally reaches its destination address. To this end, the destination address contained in the received data packet is used for comparison with the destination addresses stored in a lookup table in the router. Each destination address stored in the lookup table is linked to an output port in the router, so that in the event of a positive comparison the data packet is forwarded via the output port which is currently linked to the corresponding destination address initiating the positive comparison. Disadvantageously, a large and costly amount of memory space needs to be provided for the network's destination addresses which need to be stored in the lookup table. In addition, a large amount of time and computation involvement is required for comparing the destination address from the received data packet with each destination address stored in the lookup table.
Published European application for patent EP 1 394 999 A1 describes a method for compressing the destination addresses which need to be stored in the router's lookup table or memory. By way of example, the destination addresses are compressed losslessly using the Huffman algorithm to produce coded keys. This means that the memory space requirement for the coded keys which are to be stored is significantly reduced in comparison with destination addresses which are to be stored. However, there is also the problem that the compressed keys are not the same length, i.e. do not have a constant key bit length, on account of the Huffman coding. The inconstant key bit length of the coded keys which are to be stored gives rise to problems in the memory organization. Since coded keys with a relatively short bit length arise more frequently than coded keys with longer bit lengths on account of the Huffman algorithm used, the set of comparators which needs to be provided on account of the coded keys which arise with longer bit lengths is fully utilized only in the rarest cases. This results in a reduction in the possible throughput during address comparison.